package aha;

import java.util.Random;

/**
 * 啊哈!算法!  -- 啊哈磊 著
 * 1.1 最快最简单的排序 -- 桶排序
 * 时间复杂度: O(M+N)
 */
public class Demo1_1 {
    public static void main(String[] args) {
        int i = 0;

        // 定义分数
        int[] num = new int[5];
        Random r = new Random();
        // 随机填充
        for (i = 0; i < num.length; ) {
            num[i++] = r.nextInt(10);
        }

        // 显示分数
        System.out.print("分数: ");
        for (int n : num) {
            System.out.print(n + " ");
        }
        System.out.println();

        // 定义桶
        int[] arr = new int[10];
        // 将分数放入桶中
        for (i = 0; i < arr.length; i++) {
            for (int n : num) {
                if (n == i) {
                    arr[i]++;
                }
            }
        }

        // 显示桶
        System.out.print("桶数量: ");
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
        System.out.println("桶位置: 0 1 2 3 4 5 6 7 8 9");

        // 排序结果
        System.out.print("排序结果: ");
        for (i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i]; j++) {
                System.out.print(i + " ");
            }
        }
    }
}
